package com.shakespace.algorithm.linked_list

import kotlin.math.max

/**
 * 给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
 *
 * 请你将两个数相加，并以相同形式返回一个表示和的链表。
 *
 * 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
 */

fun main() {
    val array = intArrayOf(3, 2, 4)
    sumOfTwoNums2(array, 6)
}

// normal way
fun sumOfTwoNums(nums: IntArray, target: Int): IntArray {
    for (i in nums.indices) {
        for (j in 1..<nums.size - 1) {
            if (i != j && nums[i] + nums[j] == target) {
                return intArrayOf(i, j)
            }
        }
    }
    return intArrayOf(0, 0)
}

// [3,2,4] 6
fun sumOfTwoNums2(nums: IntArray, target: Int): IntArray {
    val map = mutableMapOf<Int, Int>()
    map[nums[0]] = 0
    for (i in 1..<nums.size) {
        if (map.keys.contains(target - nums[i])) {
            return intArrayOf(map[target - nums[i]]!!, i)
        } else {
            map[nums[i]] = i
        }
    }
    return intArrayOf(0, 0)
}